package com.yulan.dp.string;

import org.junit.Test;

/**
 * 最长上升子序列
 */
public class LIS {

    public int dp1(int[] arr){
        int len = arr.length;
        int[] dp = new int[len+1];
        int ans = 0;
        for(int i = 0; i<=len;i++)
            dp[i] = 1;

        for(int i = 1; i<len; i++){
            for(int j = 1; j<i; j++){
                if(arr[j]<arr[i])
                    dp[i] = Math.max(dp[i],dp[j]+1);
            }
        }

        for(int i = 1; i<=len; i++)
            ans = Math.max(dp[i],ans);

        return ans;
    }

    private int binary_search(int[] arr , int r ,int target){
        int l = 0;
        int index = 0;
        while (l <= r){
            int mid = (l + r)>>>1;
            if(arr[mid] >= target) {
                r = mid - 1;
                index = mid;
            }
            else l = mid + 1;
        }

        return index;
    }

    public int lengthOfLIS(int[] arr){
        if(arr == null || arr.length == 0) return 0;
        int len = arr.length;
        int ans = 0;
        int[] dp = new int[len];
        dp[0] = arr[0];
        for(int i = 1; i<len; i++){
            if(arr[i] > dp[ans]){
                dp[++ans] = arr[i];
            }else{
                dp[binary_search(dp,ans,arr[i])] = arr[i];
            }
        }
        return ans+1;
    }

    @Test
    public void test(){
        int[] arr = {4,10,4,3,8,9};
//        System.out.println(dp1(arr));
        System.out.println(lengthOfLIS(arr));
    }

}
